package 算法.leetcode.linked.tree;

import org.junit.Test;

/**
 * @author lchenglong
 * @date 2020/12/18
 */
public class LowestCommonAncestor extends TreeBase{
    @Test
    public void test() {
        Integer[] arr = new Integer[]{6,2,8,0,4,7,9,null,null,3,5};
        TreeNode root = this.create(arr);
        TreeNode p = new TreeNode(2);
        TreeNode q = new TreeNode(4);
        TreeNode res = lowestCommonAncestor(root, p, q);
        System.out.println(res.val);
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if ((root.val - p.val)*(root.val-q.val) <=0) {
            // 与根的差值相乘小于等于0 说明分别在左右子树
            return root;
        } else if (root.val < p.val && root.val <q.val) {
            return lowestCommonAncestor(root.right,p,q);
        } else {
            return lowestCommonAncestor(root.left,p,q);
        }
    }


}
